Grumpy bookstore owner

Time: O(N); Space: O(1); medium

Today, the bookstore owner has a store open for len(customers) minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3

Output: 16

Explanation:

• The bookstore owner keeps themselves not grumpy for the last 3 minutes.

• The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Notes:

• 1 <= X <= len(customers) == len(grumpy) <= 20000

• 0 <= customers[i] <= 1000

• 0 <= grumpy[i] <= 1

class Solution1(object):
    def maxSatisfied(self, customers, grumpy, X):
        """
        :type customers: List[int]
        :type grumpy: List[int]
        :type X: int
        :rtype: int
        """
        result, max_extra, extra = 0, 0, 0
        for i in range(len(customers)):
            result += 0 if grumpy[i] else customers[i]
            extra += customers[i] if grumpy[i] else 0
            if i >= X:
                extra -= customers[i-X] if grumpy[i-X] else 0
            max_extra = max(max_extra, extra)
        return result + max_extra

s = Solution1()
customers = [1,0,1,2,1,1,7,5]
grumpy = [0,1,0,1,0,1,0,1]
X = 3
assert s.maxSatisfied(customers, grumpy, X) == 16

See also:

https://leetcode.com/problems/grumpy-bookstore-owner